package org.example.study;


/**
 * @Author chaigq
 * @Date 2020/11/4 9:50
 * @Version 1.0
 */
public class testDemo {

    // 测试归并排序
    public static void main(String[] args) {
        int[] a = {49, 38, 65, 97, 76, 13, 27, 50};
        int[] b = {7, 5, 6, 4};
        sort(b, 0, b.length - 1);
        System.out.println("排好序的数组：");
        for (int e : a)
            System.out.print(e + " ");
    }

    public static void sort(int[] nums, int start, int end) {
        if (start < end) {
            // 中间位置分割
            int mid = (start + end) / 2;
            // 继续分割数组
            // 分割的左侧数组
            sort(nums, start, mid);
            // 继续分割右侧数组
            sort(nums, mid + 1, end);
            // 对数组进行排序
            mergeSort(nums, start, end, mid);
        }
    }

    public static void mergeSort(int[] nums, int left, int right, int mid) {

        int[] temp = new int[nums.length];
        // 右子数组==左侧索引
        int leftIndex = left;
        // 右子数组==左侧索引
        int rightIndex = mid + 1;
        int k = left;
//        int count = 0;
        while (leftIndex <= mid && rightIndex <= right) {
            if (nums[leftIndex] <= nums[rightIndex]) {
                temp[k++] = nums[leftIndex++];
            } else {
                temp[k++] = nums[rightIndex++];
//                count += (mid - leftIndex + 1);
            }
        }
        // 合并剩下的部分
        while (leftIndex <= mid) {
            temp[k++] = nums[leftIndex++];
        }
        while (rightIndex <= right) {
            temp[k++] = nums[rightIndex++];
        }

        //复制回原数组
        for (int i = left; i <= right; i++)
            nums[i] = temp[i];
    }
}
